package class07;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Auther: xw
 * @Create: 2022/4/1 15:09
 * @Description: 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 *                          https://leetcode-cn.com/problems/path-sum-ii/
 */
public class PathSumII {

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public static class Info{
        public boolean isSum;
        public List<Integer> list;

        public Info(boolean isSum, List<Integer> list) {
            this.isSum = isSum;
            this.list = list;
        }
    }
    public static List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<Integer> ans  = new LinkedList<>();
        precess(root,targetSum,ans);
        return res;
    }
    public static void precess(TreeNode cur, int targetSum,List<Integer> ans) {
        if (null == cur) {
            return;
        }
        ans.add(cur.val);
        if (null == cur.left && null == cur.right && targetSum - cur.val == 0) {
            res.add(new ArrayList<>(ans));

        }
        if (null != cur.left) {
            precess(cur.left, targetSum - cur.val, ans);
            ans.remove(ans.size() - 1);
        }
        if (null != cur.right) {
            precess(cur.right, targetSum - cur.val, ans);
            ans.remove(ans.size() - 1);
        }
    }


}
